栈

#1 Stack

public interface Stack<E> {

    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

2 ArrayStack

public class ArrayStack<E> implements Stack<E> {

    private Array<E> array;

    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }
 
    public ArrayStack(){
        array = new Array<>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void push(E e){
        array.addLast(e);
    }

    @Override
    public E pop(){
        return array.removeLast();
    }

    @Override
    public E peek(){
        return array.getLast();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack: ");
        res.append('[');
        for(int i = 0 ; i < array.getSize() ; i ++){
            res.append(array.get(i));
            if(i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("] top");
        return res.toString();
    }
}

---

3 栈

---

---

4 压栈Push() array.addLast(e);

public void push(E e){
        array.addLast(e);
    }
    
-----------------------------------------------------------------------------------------
      // 向所有元素后添加一个新元素
    public void addLast(E e){
        add(size, e);
    }
        
-----------------------------------------------------------------------------------------
    // 在index索引的位置插入一个新元素e
    public void add(int index, E e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        if(size == data.length)
            resize(2 * data.length);

        for(int i = size - 1; i >= index ; i --)
            data[i + 1] = data[i];

        data[index] = e;

        size ++;
    }

5 出栈Pop() array.removeLast();

  @Override
    public E pop(){
        return array.removeLast();
    }

--------------------------------------------------------
public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E ret = data[index];
        for(int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        data[size] = null; // loitering objects != memory leak

        if(size == data.length / 4 && data.length / 2 != 0)
            resize(data.length / 2);
        return ret;
    }
-------------------------------------------------------------------------------------------------

    // 从数组中删除最后一个元素, 返回删除的元素
    public E removeLast(){
        return remove(size - 1);
    }

---

6 弹出栈定元素Peek() array.getLast();

 @Override
    public E peek(){
        return array.getLast();
    }
--------------------------------------------------------------------------------------  
    
    // 获取index索引位置的元素
    public E get(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        return data[index];
    }

    public E getLast(){
        return get(size - 1);
    }

---

循环队列

循环队列(LoopQueue)

循环队列的思想和ArrayQueue优化后的MyQueue大体相同，只不过循环队列里面加入了更加巧妙的循环机制。

上例中,我们规定tail == data.length-1队列为满进行resize,但是这一次我们换一种思路。当继续向当前队列添加元素时，我们这样做：

变量tail重新回到了起点，这也就是循环队列称之为“循环”的意义所在。那么什么时候表示当前队列已满需要进行resize呢？

当front == (tail+1)%data.length，当这个条件成立时，也就说明了队列为满，需要进行扩容操作了。循环队列实现代码如下：

public class LoopQueue<E> implements Queue<E> {
    private E[]data;
    private int front;
    private int tail;
    public LoopQueue(int capacity){
        data = (E[])new Object[capacity+1];
    }
    public LoopQueue(){
        this(10);
    }
    @Override
    public int getSize(){
        if(tail<front)
            return data.length-(front-tail);
        else{
            return tail-front;
        }
    }

    public int getCapacity(){
        return data.length-1;
    }
    @Override
    public boolean isEmpty(){
        return getSize()==0;
    }

    private void resize(int newCapacity){
        E[]newData = (E[])new Object[newCapacity+1];
        for(int i=0;i<getSize();i++){
            newData[i] = data[(i+front)%data.length];
        }
        data = newData;
        tail = getSize();
        front = 0;
    }
    @Override
    public void enqueue(E e){
        if(front==(tail+1)%data.length)
            resize(2*getSize());

        data[tail] = e;
        tail = (tail+1)%data.length;
    }

    @Override
    public E dequeue(){
        E ret = data[front];
        // Loitering Object
        data[front] = null;
        front = (front+1)%data.length;
        if(getSize() == getCapacity()/4 && getCapacity()/2!=0){
            resize(getCapacity()/2);
        }
        return ret;
    }

    @Override
    public E getFront(){
        if(getSize()==0)
            throw new IllegalArgumentException("LoopQueue is empty");

        return data[front];
    }

    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("LoopQueue size:%d,capacity:%d\n",getSize(),getCapacity()));
        stringBuilder.append("front:[");
        for(int i=front;i!=tail;i=(i+1)%data.length){
            stringBuilder.append(data[i]);
            if((i+1)%data.length!=tail)
                stringBuilder.append(",");
        }
        stringBuilder.append("]tail");
        return stringBuilder.toString();
    }
}